#ifndef _LEET_H_
#define _LEET_H_
#include <iostream>
#include <queue>
#include <string.h>
#include <string>
#include <vector>
#define DEBUG 0;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode { 
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class TestCode{
private:
	static const char* error;
	static std::vector<ListNode*> memoList;
	static std::vector<TreeNode*> memoTree;
	static std::vector<std::vector<std::vector<int>>*> arrarr;
	static std::vector<std::vector<int>*> arr;
	static std::vector<std::vector<std::string>*> arrStr;
	static std::vector<std::vector<char>*> arrChr;
	static TestCode example;
	TestCode(){};
	~TestCode()
	{
		for(unsigned i=0;i<memoList.size();i++)
			deleteList(memoList[i]);
		for(unsigned j=0;j<memoTree.size();j++)
			deleteTree(memoTree[j]);
		for(unsigned i=0;i<arr.size();i++)
			delete arr[i];
	}
	void deleteList(ListNode* root)
	{
		ListNode* now=root;
		while(now!=NULL)
		{
			root=now;
			now=now->next;
			delete root;
		}
	}
	void deleteTree(TreeNode* root)
	{
		if(root==NULL)
			return;
		if(root->left!=NULL)
			deleteTree(root->left);
		if(root->right!=NULL)
			deleteTree(root->right);
		delete root;
	}
public:
	enum Type{
		ARRAY=0,LIST,TREE,
	};
	enum ArrType{
		CHAR=0,STRING
	};
	static TreeNode* createTree(const char* data){
		if(data==NULL)
			return NULL;
		while(*data==' ')
			data++;
		if(*data!='[')
			return NULL;
		return createTree(std::string(data+1));
	}
	static ListNode* createList(const char* data){
		if(data==NULL)
			return NULL;
		while(*data==' ')
			data++;
		if(*data!='[')
			return NULL;
		return createList(std::string(data+1));
	}
	static void* createStruct(Type dataType,const char* data)
	{
		if(data==NULL)
			return NULL;
		while(*data==' ')
			data++;
		if(*data!='[')
			return NULL;
		switch(dataType)
		{
		case ARRAY:
			data++;
			while(*data==' ')
				data++;
			if(*data=='[')
			{
				std::vector<std::vector<int>>* result=new std::vector<std::vector<int>>();
				if(result==NULL)
				{
					error="malloc worng";
					return NULL;
				}
				arrarr.push_back(result);
				createArrTwo(*result,std::string(data+1));
				return result;
			}
			else
			{
				std::vector<int>* result=new std::vector<int>();
				if(result==NULL)
				{
					error="malloc worng";
					return NULL;
				}
				arr.push_back(result);
				createArrayOne(*result,std::string(data));
				return result;
			}
			break;
		case TREE:
			return createTree(std::string(data+1));
		case LIST:
			return createList(std::string(data+1));
		}
		return NULL;
	}
	static void* createCharArray(ArrType type,std::string data)
	{
		void* result=NULL;
		char* word=new char[data.size()+1],*begin=word,*end=word;
		memset(word,0,sizeof(char)*data.size()+1);
		strcpy(word,data.c_str());
		begin=strchr(word,'\"');
		if(begin==NULL)
		{
			error="text wrong";
			return NULL;
		}
		switch(type)
		{
		case CHAR:
			result=new std::vector<char>;
			arrChr.push_back((std::vector<char>*)result);
			while(begin!=NULL)
			{
				((std::vector<char>*)result)->push_back(*(begin+1));
				begin=strchr(begin+1,'\"');
				if(begin==NULL)
					return result;
				begin=strchr(begin+1,'\"');
			}
			break;
		case STRING:
			result=new std::vector<std::string>;
			arrStr.push_back((std::vector<std::string>*)result);
			end=strchr(begin+1,'\"');
			if(end==NULL)
			{
				error="text wrong";
				return NULL;
			}
			while(begin!=NULL&&end!=NULL)
			{
				((std::vector<std::string>*)result)->push_back(std::string(begin+1,end-1));
				begin=strchr(end+1,'\"');
				if(begin==NULL)
					return result;
				end=strchr(begin+1,'\"');
			}
			break;
		}
		return result;
	}
	static inline const char* lastError()
	{
		return error;
	}
private:
    static TreeNode* createTree(std::string data) {
		char* word=new char[data.size()+1];
		memset(word,0,sizeof(char)*data.size()+1);
		strcpy(word,data.c_str());
		char* p=strtok(word,",");
        if(data.size()==0)
			return NULL;
		std::queue<TreeNode**> que;
		TreeNode* root=NULL;
		que.push(&root);
		while(p)
		{
			auto temp=que.front();
			que.pop();
			if(strcmp(p,"null")==0)
				*temp=NULL;
			else
			{
				*temp=new TreeNode;
				if(temp==NULL)
				{
					error="malloc wrong";
					delete[] word;
					return NULL;
				}
				if(sscanf(p,"%d",&(*temp)->val)<=0)
				{
					error="data wrong";
					delete[] word;
					return NULL;
				}
				que.push(&(*temp)->left);
				que.push(&(*temp)->right);
			}
			p=strtok(NULL,",");
		}
		delete[] word;
		memoTree.push_back(root);
		return root;
    }
	static ListNode* createList(std::string data)
	{
		char* word=new char[data.size()+1];
		memset(word,0,sizeof(char)*data.size()+1);
		strcpy(word,data.c_str());
		char* p=strtok(word,",");
        if(data.size()==0)
			return NULL;
		ListNode* root=NULL,*now=NULL,*temp=NULL;
		while(p!=NULL)
		{
			int val=0;
			if(sscanf(p,"%d",&val)<=0)
				return NULL;
			temp=new ListNode(val);
			if(temp==NULL)
			{
				error="malloc wrong";
				delete[] word;
				return NULL;
			}
			if(now!=NULL)
			{
				now->next=temp;
				now=now->next;
			}
			else
			{
				now=temp;
				root=temp;
			}
			p=strtok(NULL,",");
		}
		delete[] word;
		memoList.push_back(root);
		return root;
	}
	static void createArrayOne(std::vector<int>& arr,std::string data)
	{
		char* word=new char[data.size()+1];
		memset(word,0,sizeof(char)*data.size()+1);
		strcpy(word,data.c_str());
		char* p=strtok(word,",");
		while(p!=NULL)
		{
			int val=0;
			if(sscanf(p,"%d",&val)<=0)
			{
				error="fmt wrong";
				delete[] word;
				return;
			}
			arr.push_back(val);
			p=strtok(NULL,",");
		}
		delete[] word;
	}
	static void createArrTwo(std::vector<std::vector<int>>& arr,std::string data)
	{
		char* word=new char[data.size()+1];
		std::vector<int> now;
		memset(word,0,sizeof(char)*data.size()+1);
		strcpy(word,data.c_str());
		char* p=word,*next=strstr(p+1,"[");
		while(p!=NULL)
		{
			if(next!=NULL)
				*next=0;
			createArrayOne(now,std::string(p));
			arr.push_back(now);
			now.clear();
			if(next==NULL)
				break;
			p=next+1;
			next=strstr(p+1,"[");
		}
		delete[] word;
	}
};
const char* TestCode::error=NULL;
std::vector<ListNode*> TestCode::memoList;
std::vector<TreeNode*> TestCode::memoTree;
TestCode TestCode::example;
std::vector<std::vector<std::vector<int>>*> TestCode::arrarr;
std::vector<std::vector<int>*> TestCode::arr;
std::vector<std::vector<std::string>*> TestCode::arrStr;
std::vector<std::vector<char>*> TestCode::arrChr;
#ifdef DEBUG
std::string serialize(TreeNode* root) {
	if(root==NULL)
		return "[]";
	std::queue<TreeNode*> que;
	std::string result="[";
	que.push(root);
	while(!que.empty())
	{
		TreeNode* temp=que.front();
		que.pop();
		if(temp==NULL)
			result+="null,";
		else
		{
			que.push(temp->left);
			que.push(temp->right);
			result+=std::to_string(temp->val)+",";
		}
	}
	result.erase(result.end()-1);
	for(int i=result.size()-1;i>=0;i--)
		if(result[i]>='0'&&result[i]<='9')
		{
			result.erase(result.begin()+i+1,result.end());
			break;
		}
	result+="]";
	return result;
}
std::string travelList(ListNode* node)
{
	std::string result;
	result="[";
	while(node!=NULL)
	{
		result+=std::to_string(node->val)+",";
		node=node->next;
	}
	if(result[result.size()-1]==',')
		result.erase(result.end()-1);
	result+="]";
	return result;
}
#endif
#endif
